package com.atguigu.ssyx.product;

import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Test;
import org.springframework.boot.test.context.SpringBootTest;

/**
 * @author 杨林
 * @create 2023-07-20 17:22 星期四
 * description:一些排序操作的练习
 */
@SpringBootTest
@Slf4j
public class SortTest01 {

    /**
     *  测试冒泡排序
     */
    @Test
    public void testBubbleSort(){ 
        Integer[] arr = {9,8,4,7,6,2};
        this.bubbleSort(arr);
        for (Integer integer : arr) {
            System.out.println(integer);
        }
    }


    /**
     * 测试快速排序
     */
    @Test
    public void testQuickSort(){
        Integer[] arr = {9,8,4,7,6,2};
        this.quickSort(arr,0,arr.length - 1);
        for (Integer integer : arr) {
            System.out.println(integer);
        }
    }


    /**
     * 冒泡排序：
     *  算法描述：
     *      比较相邻的元素，如果前一个比后一个大，就交换两个元素的位置
     *      对每一对相邻的元素做同样的工作，从开始第一对到结尾最后一对，在经过一轮排序后，最大的元素就放在了最后一位
     *      针对所有元素重复以上步骤，除了最后一个
     *      重复上述三个步骤，直到排序完成
     *  如果两个元素相等，不会在交换位置，所以冒泡排序是一种稳定的排序算法。
     * @param data
     */
    private void bubbleSort(Integer[] data){
        for (int i = 1;i < data.length;i++){
            for (int j = 0;j < data.length - i;j++){
                if (data[j + 1] < data[j]){  //如果后一个元素小于前一个元素，则交换两个元素
                    int tmp = data[j + 1];
                    data[j + 1] = data[j];
                    data[j] = tmp;
                }
            }
        }       
    }

    /**
     * 快速排序：
     *  算法描述：
     *      使用分治思想来把一个串分割成两个字串：
     *          从数组中挑一个元素，成为基准点（pivot）
     *          重新排序数列，所有元素比基准点小的放在基准点前面，比基准点大的放在基准点后面（相同的可放在任意一边）
     *          在这个分区退出以后，该基准点就处于数列的中间位置。这个称为分区操作：
     *          递归地把小于基准值元素的子数列和大于基准值元素的子数列排序
     *   data:要排序的数组
     *   low：数组的头部索引
     *   height：数组的尾部索引
     */
    public void quickSort(Integer[] data,Integer low,Integer height){
        int i,j,temp,t;
        if (height < low){  //数组尾部索引值 < 数组头部索引值  表示该数组不存在   （也可视作递归的终止条件）
            return;
        }
        i = low;
        j = height;
        //temp就是基准位，假设数组最左边的元素作为基准位（基准位可以选取数组中任意元素）
        temp = data[low];
        log.info("基准位元素是：{}",temp);
        while (i < j){ 
            //先看右边，依次往左递增  
            while (temp <= data[j] && i < j){
                j--;
            }
            //在看左边，依次往右递增
            while (temp >= data[i] && i < j){
                i++;
            }
            //如果满足下列条件，就交换i,j位置的元素
            if (i < j){
                log.info("开始交换元素：{} 和元素{}的位置",data[i],data[j]);
                t = data[i];
                data[i] = data[j];
                data[j] = t;
                log.info("交换后的数组为：{}",data);
            }
        }
        //当i j相遇时，将基准位和i j相遇位置的元素交换
        log.info("基准位和i、j相遇位置的元素交换");
        data[low] = data[i];
        data[i] = temp;
        log.info("交换完成之后的数组为：{}",data);
        //递归调用左边的数组
        quickSort(data,low,j - 1);
        //递归调用右边数组
        quickSort(data,j + 1,height);
    }


    /**
     * 归并排序：
     *  算法描述：
     *      把长度为n的数组序列分成两个长度为n/2的数组序列
     *      对这两个子序列分别采用归并排序
     *      将两个排序好的子序列合并成一个最终的排序序列
     */
    private void mergeSort(){
        
    }


    /**
     * 二分查找：
     *  算法描述：
     *      首先，需要数组中的元素是有序的，将数组中间位置记录的关键字与查找的关键字进行比较，如果两者相等，则查找成功
     *      否则，利用中间位置记录将表分成前、后两个子表，如果中间位置的关键字大于查找的关键字，则进一步查找前一子表，否则查找后一子表
     *      重复上诉过程，直到找到满足条件的记录，或则查询子表不存在为止
     * @return
     */
    private Integer binarySearch(){
     
        
        return null;
    }
}
